public class Trap {

    public static void main(String[] args) {
        int[] nums = {0,1,0,2,1,0,1,3,2,1,2,1};
        Trap trap = new Trap();
        System.out.println(trap.trap(nums));
    }

    public int trap2(int[] height) {
        int n = height.length;
        if (n == 1) return 0;
        int[] dp = new int[n];
        dp[0] = height[0];
        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            int k = dp[i - 1] - height[i];
            if (k <= 0) {
                dp[i] = height[i];
            } else {
                if (dp[i - 1] - height[i - 1] > 0) {
                    dp[i] = dp[i -1];
                    ans += dp[i] - height[i];
                } else {
                    int max = height[i];
                    for (int j = i + 1; j < n - 1; j++) {
                        max = Math.max(max, height[j]);
                    }
                    int min = Math.min(max, dp[i - 1]);
                    ans += min - height[i];
                    dp[i] = min;
                }
            }
        }
        return ans;
    }

    public int trap(int[] height) {
        int n = height.length;
        if (n == 1 || n == 2) return 0;
        int l = 1;
        int r = n - 2;
        int maxL = height[0];
        int maxR = height[n - 1];
        int ans = 0 ;
        while (l <= r) {
            if (maxL <= maxR) {
                ans += Math.max(0, maxL - height[l]);
                maxL = Math.max(maxL, height[l]);
                l++;
            } else {
                ans += Math.max(0, maxR - height[r]);
                maxR = Math.max(maxR, height[r]);
                r--;
            }
        }
        return ans;
    }
}
